package Hard;

import java.util.*;
import java.util.stream.Collectors;

// 1473.粉刷房子
/*
 * 思：
 * 如果房子数为0则直接返回-1
 * 先数出已有街区machi ，如果已有街区大于target，直接返回-1
 * M=target-machi代表还需要的街区数量
 * 如果M = 0,则答案唯一,直接计算即可 ---> 不对，如果M = 0 答案也不一定唯一
 *      e.g houses[1,2,0,1,1] target=3 M=0  ,此时0可以被刷成1也可以被刷成2
 * 否则题目化简为，在剩余的所有没上色的房子houses里，划分M个街区的最小消耗
 * 开始时，当前已有街区cur为0
 * 从houses[0]里选择最小cost，cur = 1
 * 每次从houses[i]里选择最小的cost，如果颜色发生了变化，则cur+1。 houses[i]最多有M-cur种选择，所以要分别对这些选择进行讨论
 * 所以是深搜的思路
 * ---------------------------
 * AC: 9/60. 超出时间限制
 * 改进，剪枝： 失败了！
 * */
public class Solution1473 {
    public static void main(String[] args) {
        int[] houses = new int[]{0, 0, 0, 3};
        int[][] cost = new int[][]{{2, 2, 5}, {1, 5, 5}, {5, 1, 2}, {5, 2, 5}};
        System.out.println(minCost(houses, cost, 4, 3, 3));
    }
    public static int minCost(int[] houses, int[][] cost, int m, int n, int target) {
        if (m == 0)
            return -1;
        // 没有上色的房子的数量
        int house = 0;
        // 已有街区
        int cur = 0;
        // 上一个颜色
        int lastColor = 0;
        int allCost = 0;
        int[] minCost = new int[1];
        minCost[0] = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            if (houses[i] != 0)
                house++;
            if (cur == 0 && houses[i] != 0) {
                cur = 1;
                lastColor = houses[i];
            } else if (houses[i] != 0 && houses[i] != lastColor) {
                cur++;
                lastColor = houses[i];
            }
        }
        // 还需要的街区数量M
        int M = target - cur;
        // 特别注意，如果新刷的房子和前面那个房子连起来都是同一种颜色，那么M不减1，如果不一样，则+1
        // eg. houses[0,1,0,1,0,0,0]，target = 3 则初始M = 2
        //   如果刷成了[1,1,0,1,0,0,0]，刷了一个1以后，M应该变为1，但它和已有街区衔接，因此M+1，仍然为2
        dfs(houses, cost, M, allCost, 0, minCost);
        return minCost[0] == Integer.MAX_VALUE ? -1 : minCost[0];
    }

    // cur代表当前该刷的房子
    public static void dfs(int[] houses, int[][] cost, int M, int allCost, int cur, int[] minCost) {
        // dfs每次选择最小的消耗(因为dfs要讨论所有的消耗情况，因此没必要每次选择最小的消耗)
        // 递归结束条件,全部房子上完色
        if (cur == houses.length && M == 0) {
            minCost[0] = Math.min(minCost[0], allCost);
            return;
        } else if (cur == houses.length || M < 0) {
            return;
        }
        if (houses[cur] != 0) {
            dfs(houses, cost, M, allCost, cur + 1, minCost);
        } else {
            for (int i = 0; i < cost[cur].length; i++) {
                // 分别递归选择第i+1种颜色的消耗情况
                houses[cur] = i + 1;
                int Q = 1;
                // 如果当前房子与前面的颜色相同或者后面的颜色不为0且和这个房子颜色相同，则Q=0
                if ((cur - 1 >= 0 && houses[cur - 1] == houses[cur]) || (cur + 1 < houses.length && houses[cur + 1] == houses[cur]))
                    Q = 0;
                dfs(houses, cost, M - Q, allCost + cost[cur][i], cur + 1, minCost);
                houses[cur] = 0;
            }
        }

    }





    public static int minCost_jianzhi(int[] houses, int[][] cost, int m, int n, int target) {
        if (m == 0)
            return -1;
        // 没有上色的房子的数量
        int house = 0;
        // 已有街区
        int cur = 0;
        // 上一个颜色
        int lastColor = 0;
        int allCost = 0;
        int[] minCost = new int[1];
        minCost[0] = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            if (houses[i] != 0)
                house++;
            if (cur == 0 && houses[i] != 0) {
                cur = 1;
                lastColor = houses[i];
            } else if (houses[i] != 0 && houses[i] != lastColor) {
                cur++;
                lastColor = houses[i];
            }
        }
        // 还需要的街区数量M
        int M = target - cur;
        // 特别注意，如果新刷的房子和前面那个房子连起来都是同一种颜色，那么M不减1，如果不一样，则+1
        // eg. houses[0,1,0,1,0,0,0]，target = 3 则初始M = 2
        //   如果刷成了[1,1,0,1,0,0,0]，刷了一个1以后，M应该变为1，但它和已有街区衔接，因此M+1，仍然为2
        dfs_jianzhi(houses, cost, M, allCost, 0, minCost);
        return minCost[0] == Integer.MAX_VALUE ? -1 : minCost[0];
    }

    // cur代表当前该刷的房子
    public static void dfs_jianzhi(int[] houses, int[][] cost, int M, int allCost, int cur, int[] minCost) {
        // dfs每次选择最小的消耗(因为dfs要讨论所有的消耗情况，因此没必要每次选择最小的消耗)
        // 剪枝：不能全部讨论，只讨论前M种消耗最小的情况！
        // 递归结束条件,全部房子上完色
        if (cur == houses.length && M == 0) {
            minCost[0] = Math.min(minCost[0], allCost);
            return;
        } else if (cur == houses.length || M < 0) {
            return;
        }
        if (houses[cur] != 0) {
            dfs(houses, cost, M, allCost, cur + 1, minCost);
        } else {
            int[][] selectCost = new int[M][2];
            // 先找出M种消耗最小的情况
            // 想排序以后保留坐标，则使用map自带的堆排序
            Map map = new LinkedHashMap<>();
            for (int i = 0; i < cost[cur].length; i++) {
                map.put(i, cost[cur][i]);
            }
            LinkedHashMap integerIntegerMap = (LinkedHashMap) sortMapByValues(map);
            for (int i = 0; i < M; i++) {
                Map.Entry next = (Map.Entry) integerIntegerMap.entrySet().iterator().next();
                selectCost[i][0] = (int) next.getKey();
                selectCost[i][1] = (int) next.getValue();
                map.remove(selectCost[i][0]);
            }


            for (int i = 0; i < M; i++) {
                // 分别递归选择第i+1种颜色的消耗情况
                // 剪枝：只递归前M种消耗最小的情况
                houses[cur] = selectCost[i][0] + 1;
                int Q = 1;
                // 如果当前房子与前面的颜色相同或者后面的颜色不为0且和这个房子颜色相同，则Q=0
                if ((cur - 1 >= 0 && houses[cur - 1] == houses[cur]) || (cur + 1 < houses.length && houses[cur + 1] == houses[cur]))
                    Q = 0;
                dfs(houses, cost, M - Q, allCost + selectCost[i][1], cur + 1, minCost);
                houses[cur] = 0;
            }
        }
    }

    // Map按照value排序
    public static <K extends Comparable, V extends Comparable> Map<K, V> sortMapByValues(Map<K, V> aMap) {
        HashMap<K, V> finalOut = new LinkedHashMap<>();
        aMap.entrySet()
                .stream()
                .sorted((p1, p2) -> p2.getValue().compareTo(p1.getValue()))
                .collect(Collectors.toList()).forEach(ele -> finalOut.put(ele.getKey(), ele.getValue()));
        return finalOut;
    }

}
